package q652_findDuplicateSubtrees;

import CommonClass.Pair;
import CommonClass.TreeNode;

import java.util.*;

public class Solution {
    Map<String, Pair<TreeNode, Integer>> seen = new HashMap<>();
    Set<TreeNode> repeat = new HashSet<>();
    int idx = 0;
    /*
    可以用一个三元组直接表示一棵子树，即 (x,l,r)，它们分别表示：
    根节点的值为 x；
    左子树的序号为 l；
    右子树的序号为 r。
    这里的「序号」指的是：每当我们发现一棵新的子树，就给这棵子树一个序号，用来表示其结构。
    那么两棵树是重复的，当且仅当它们对应的三元组完全相同。
    使用「序号」的好处在于同时减少了时间复杂度和空间复杂度。
    使用序号替换整个左子树和右子树的序列，可以使得每一个节点只使用常数大小的空间。
     */
    public List<TreeNode> findDuplicateSubtrees(TreeNode root) {
        dfs(root);
        return new ArrayList<>(repeat);
    }

    public int dfs(TreeNode node) {
        if (node == null) {
            return 0;
        }
        int[] tri = {node.val, dfs(node.left), dfs(node.right)};
        String hash = Arrays.toString(tri);
        if (seen.containsKey(hash)) {
            Pair<TreeNode, Integer> pair = seen.get(hash);
            repeat.add(pair.getKey());
            return pair.getValue();
        } else {
            seen.put(hash, new Pair<>(node, ++idx));
            return idx;
        }
    }

}
